using System;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0130. 被围绕的区域")]
    public class No0130_Solve : AbsBaseTestItem
    {
        /*
        给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
        找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
        */

        public override void OnTest()
        {
            bool EqualsFun(char[][] r1, char[][] r2) => r1.ToJSONString() == r2.ToJSONString();
            char[][] Calc(char[][] board)
            {
                Solve(board);
                return board;
            }

            Assert.TestExe(Calc,
                new char[][] {
                    new char[] {'X','X','X','X',},
                    new char[] {'X','O','O','X',},
                    new char[] {'X','X','O','X',},
                    new char[] {'X','O','X','X',},
                },
                equalsMethod: EqualsFun,
                new char[][] {
                    new char[] {'X','X','X','X',},
                    new char[] {'X','X','X','X',},
                    new char[] {'X','X','X','X',},
                    new char[] {'X','O','X','X',},
                });
        }

        public void Solve(char[][] board)
        {
            int n, m;
            n = board.Length;
            if (n == 0)
            {
                return;
            }
            m = board[0].Length;
            for (int i = 0; i < n; i++)
            {
                dfs(board, i, 0);
                dfs(board, i, m - 1);
            }
            for (int i = 1; i < m - 1; i++)
            {
                dfs(board, 0, i);
                dfs(board, n - 1, i);
            }
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (board[i][j] == 'A')
                    {
                        board[i][j] = 'O';
                    }
                    else if (board[i][j] == 'O')
                    {
                        board[i][j] = 'X';
                    }
                }
            }
            void dfs(char[][] board, int x, int y)
            {
                if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O')
                {
                    return;
                }
                board[x][y] = 'A';
                dfs(board, x + 1, y);
                dfs(board, x - 1, y);
                dfs(board, x, y + 1);
                dfs(board, x, y - 1);
            }
        }
    }
}
